/* 
 *  Copyright (c) 2012 Shirou Maruyama
 * 
 *   Redistribution and use in source and binary forms, with or without
 *   modification, are permitted provided that the following conditions
 *   are met:
 * 
 *   1. Redistributions of source code must retain the above Copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above Copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 *   3. Neither the name of the authors nor the names of its contributors
 *      may be used to endorse or promote products derived from this
 *      software without specific prior written permission.
 */

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <stdint.h>
#include "dictionary.hpp"

using namespace std;

namespace pacbeep {

  uint32_t DICT::ComputeHashVal(const uint32_t left, const uint32_t right) const {
    return (left*(right+3)) & EntrySize_;
  }

  void DICT::Init(const uint64_t k) {
    Delta_ = 0;
    N_ = 0;
    K_ = k;
    NumRules_ = 256;
    EntrySize_ = (2 << 10) - 1;
    vector<vector<RULE> >(EntrySize_).swap(Rules_);
  }

  bool DICT::GetCode(const uint32_t left, const uint32_t right, uint32_t& code) {
    ++N_;
    bool ret = true;
    if ((code = ReverseAccess(left, right)) == kDummy) {
      code = AddRule(left, right);
      ret = false;
    }
    if (N_/K_ > Delta_) {
      ReDict();
      ++Delta_;
    }
    return ret;
  }

  uint32_t DICT::AddRule(const uint32_t left, const uint32_t right) {
    RULE new_rule(NumRules_++, left, right, Delta_ + 1);
    uint32_t h = ComputeHashVal(left, right);
    Rules_[h].push_back(new_rule);
    if (++DictSize_ > EntrySize_*20) {
      ReHash();
    }
    return new_rule.code;
  }

  uint32_t DICT::ReverseAccess(const uint32_t left, const uint32_t right) {
    uint32_t h = ComputeHashVal(left, right);
    for (uint32_t i = 0; i != Rules_[h].size(); ++i) {
      if (Rules_[h][i].left == left && 
	  Rules_[h][i].right == right) {
	++Rules_[h][i].cnt;
	return Rules_[h][i].code;
      }
    }
    return kDummy;
  }

  void DICT::ReDict() {
    DictSize_ = 0;
    for (uint32_t i = 0; i != Rules_.size(); ++i) {
      vector<RULE> new_elems(0);
      for (uint32_t j = 0; j != Rules_[i].size(); ++j) {
	if (Rules_[i][j].cnt > Delta_)
	  new_elems.push_back(Rules_[i][j]);
      }
      Rules_[i].swap(new_elems);
      DictSize_ += Rules_[i].size();
    }
   }

  void DICT::ReHash() {
    ++EntrySize_;
    EntrySize_ = (EntrySize_ << 1UL) - 1UL;
    vector<vector<RULE> > new_rules(EntrySize_);
    for (uint32_t i = 0; i != Rules_.size(); ++i) {
      for (uint32_t j = 0; j != Rules_[i].size(); ++j) {
	uint32_t h = ComputeHashVal(Rules_[i][j].left, Rules_[i][j].right);
	new_rules[h].push_back(Rules_[i][j]);
      }
      vector<RULE>().swap(Rules_[i]);
    }
    Rules_.swap(new_rules);
  }
} // namespace pacbeep

